# 141. 环形链表
# 给定一个链表，判断链表中是否有环。

# 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，
# 我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

# 如果链表中存在环，则返回 true 。 否则，返回 false 。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:

    # 冒号是 Python 3.5 增加的，用于描述参数的类型
    # ->常常出现在python函数定义的函数名后面，为函数添加元数据,描述函数的返回类型，从而方便开发人员使用
    def hasCycle(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return False
        p = head
        q = head.next  # 快指针2步每次，如果有环肯定能相遇
        while p is not None and q is not None:
            if p == q:
                return True
            if p.next is None or q.next is None:
                return False
            p = p.next
            q = q.next.next

            # 能执行到这里说明没有有环
        return False


class SingleLinkList:
    def __init__(self, node=None):
        if node is None:
            head_node = ListNode(0)
            self.head = head_node
        else:
            self.head = node


# 输入：head = [3,2,0,-4], pos = 1
node1 = ListNode(3)
link_list = SingleLinkList()
link_list.head = node1
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1
s = Solution()
print(node1.val)
print(s.hasCycle(node1))
